package tree.leetcode_236_medium;

import java.util.List;

public class lowestCommonAncestor {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.left.left = new TreeNode(76);
        root.left.right = new TreeNode(21);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        TreeNode treeNode = lowestCommonAncestor(root, root.left.left, root.left.right);
        System.out.println(treeNode.val);
    }

    public static void printList(List<Integer> list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /**
         * root == null 越过叶子结点返回 null
         * root == p    p就是最近公共祖先
         * root == q    q就是最近公共祖先
         */
        if (root == null || root == p || root == q) {
            return root;
        }
        //对左子树进行递归，寻找是否含有p或q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        //对右子树进行递归，寻找是否含有p或q
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        //左右都不存在，则说明root的左/右都不包含p或q
        if (left == null && right == null) {
            return null;
        }
        //左子树没有p或q，就在右子树中
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }

        //左中发现了p或q，右中发现了p或q，说明最近公共祖先分列在root的两侧，root就是最近公共祖先
        return root;    //if(left != null && right != null)
    }
}
